#define _CRT_SECURE_NO_WARNINGS 1

#include"Path.h"

int visited[MAXV];

void PathAll1(AdjGraph* G, int u, int v, int path[], int d)
{
	ArcNode* p = nullptr;
	int j = 0, w = 0;
	d++;
	path[d] = u;
	visited[u] = 1;
	if (u == v && d > 0)
	{
		for (j = 0; j <= d; j++)
		{
			printf("%3d", path[j]);
		}
		cout << endl;
		visited[u] = 0;
		return;
	}
	p = G->adjlist[u].firstarc;
	while (p != NULL)
	{
		w = p->adjvex;
		if (visited[w] == 0)
		{
			PathAll1(G, w, v, path, d);
		}
		p = p->nextarc;
	}
	visited[u] = 0;
}

void PathAll2(AdjGraph* G, int u, int v, int l, int path[], int d)
{
	ArcNode* p = nullptr;
	int i = 0, w = 0;
	d++;
	path[d] = u;
	visited[u] = 1;
	if (u == v && d == l)
	{
		for (i = 0; i <= d; i++)
		{
			printf("%3d", path[i]);
		}
		cout << endl;
		visited[u] = 0;
		return;
	}
	p = G->adjlist[u].firstarc;
	while (p != NULL)
	{
		w = p->adjvex;
		if (visited[w] == 0)
		{
			PathAll2(G, w, v, l, path, d);
		}
		p = p->nextarc;
	}
	visited[u] = 0;
}

int ShortPath(AdjGraph* G, int u, int v, int path[])
{
	struct
	{
		int vno;
		int level;
		int parent;
	}qu[MAXV];
	int front = -1, rear = -1, k = 0, lev = 0, i = 0, j = 0;
	ArcNode* p = nullptr;
	visited[u] = 1;
	rear++;
	qu[rear].vno = u;
	qu[rear].level = 0;
	qu[rear].parent = -1;
	while (front < rear)
	{
		front++;
		k = qu[front].vno;
		lev = qu[front].level;
		if (k == v)
		{
			i = 0;
			j = front;
			while (j != -1)
			{
				path[lev - i] = qu[j].vno;
				j = qu[j].parent;
				i++;
			}
			return lev;
		}
		p = G->adjlist[k].firstarc;
		while (p != NULL)
		{
			if (visited[p->adjvex] == 0)
			{
				visited[p->adjvex] = 1;
				rear++;
				qu[rear].vno = p->adjvex;
				qu[rear].level = lev + 1;
				qu[rear].parent = front;
			}
			p = p->nextarc;
		}
	}
	return -1;
}